package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         8.13,
		Discription: "最多能叠多高的箱子",
		Level:       3,
		Labels: map[string]int{
			"多元排序":  1,
			"动态规划": 1,
		},
	})
}

//转化为求递增子序列之和的最大值
func PileBox(box [][]int) int {
	//排序是为了保证右边的箱子不可能会放在左边箱子底下
	//只按一个维度排序即可，但为了保险还是这样排
	sort.Slice(box, func(i, j int) bool {
		if box[i][0] != box[j][0] {
			return box[i][0] > box[j][0]
		} else if box[i][1] != box[j][1] {
			return box[i][1] > box[j][1]
		} else {
			return box[i][2] > box[j][2]
		}
	})

	dp := make([]int, len(box))
	dp[0] = box[0][2]
	res := 0
	for j := 1; j < len(box); j++ {
		dp[j] = box[j][2]
		for i := j - 1; i >= 0; i-- {
			if box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2] {
				dp[j] = max(dp[j], box[j][2]+dp[i])
			}
		}
		res = max(res, dp[j])
	}

	return res
}
